package com.btashov.stringarray;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Bahtiyar Tashov <btashov@gmail.com>
 */

/**
 * Py code
 * <pre><code>
  A--
  O(LogN)

  def isAnagram1(str1, str2):
      return sorted(getLetters(str1))==sorted(getLetters(str2))

  def getLetters(text):
      return [char.lower() for char in text if char in string.letters]

  B--
  O(N)

  def isAnagram2(str1, str2):
      str1, str2 = getLetters(str1), getLetters(str2)
      if len(str1)!=len(str2):
          return False
      counts=collections.defaultdict(int)
      for letter in str1:
          counts[letter]+=1
      for letter in str2:
          counts[letter]-=1
          if counts[letter]<0:
              return False
      return True

 Does he expect?

  a low-level, highly optimized algorithm (as you are attempting)
  or does he want to see, that I can apply the standard Java API to the problem (as Landei suggests)
  or maybe something in between, like the optimized implementation and use of a multi-set/counted set/bag (as Bart and Scott do)

  Possibly the interviewer just expects you to discuss exactly that with him,
  so that he sees that you know that these alternatives exist and which advantages and disadvantages they have.

 * </code></pre>
 */
public class Anagram {

    public static boolean anagram(String s, String t) {

        if (s.length() != t.length()) {
            return false;
        }

        int[] letters = new int[256];
        int numUniqueCharS = 0;
        int numCompletedT = 0;
        char[] chars = s.toLowerCase().toCharArray();

        for (char c : chars) { // count number of each char in s.
            if (letters[c] == 0) {
                ++numUniqueCharS;
            }
            ++letters[c];
        }
        for (int i = 0; i < t.length(); ++i) {
            int c = (int) t.charAt(i);
            if (letters[c] == 0) { // Found more of char c in t than in s.
                return false;
            }
            --letters[c];
            if (letters[c] == 0) {
                ++numCompletedT;
                if (numCompletedT == numUniqueCharS) {
                    // it’s a match if t has been processed completely
                    return i == t.length() - 1;
                }
            }
        }
        return false;
    }

    /*
    B--
     O(N)

     def isAnagram2(str1, str2):
         str1, str2 = getLetters(str1), getLetters(str2)
         if len(str1)!=len(str2):
             return False

         counts=collections.defaultdict(int)

         for letter in str1:
             counts[letter]+=1
         for letter in str2:
             counts[letter]-=1
             if counts[letter]<0:
                 return False
         return True
    */
    public static boolean isAnagram(String strA, String strB) {
        if (strA.length() != strB.length()) {
            return false;
        }

        int[] letters = new int[256];
        int numUniqueChar = 0;
        char[] chars = strA.toLowerCase().toCharArray();

        for (char c : chars) {         //count number of each char in s
            if (letters[c] == 0) {
                ++numUniqueChar;
            }
            ++letters[c];
        }

        int numCompleted = 0;
        for (int i = 0; i < strB.length(); ++i) {
            int indChB = (int) strB.charAt(i);
            if (letters[indChB] == 0) {
                return false;
            }
            --letters[indChB];

            if (letters[indChB] == 0) {
                ++numCompleted;
                if (numCompleted == numUniqueChar) {
                    return i == strB.length() - 1;
                }
            }
        }
        return false;
    }

    public static boolean isAnagramBySort(String strA, String strB) {
        return strA.length() == strB.length() && Arrays.equals(cleanedArrayOfLetters(strA), cleanedArrayOfLetters(strB));
    }

    private static Object[] cleanedArrayOfLetters(String str) {

        char[] inputChars = str.toLowerCase().toCharArray();
        List<Character> list = new LinkedList<Character>();

        for (int i = 0; i < inputChars.length; ++i) {
            if (Character.isLetter(inputChars[i])) {
                list.add(inputChars[i]);
            }
        }
        Collections.sort(list);

        return list.toArray();
    }

    public static boolean isAnagramBySortNotOptimize(String strA, String strB) {
        return Arrays.equals(cleanedArrayOfLetters(strA), cleanedArrayOfLetters(strB));
    }
}
